package arithmetic1.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

/*
    基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
//        int arr[]={6,1,68,3,9,32};

        int arr[]=new int[8000000];

        for (int i = 0; i < arr.length; i++) {
            arr[i]= (int) (Math.random()*800000);
        }
        Date date=new Date();
        SimpleDateFormat sdf=new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
        String time1 = sdf.format(date);
        System.out.println("排序前的时间:"+time1);

        radixSort(arr);

        date=new Date();
        String time2=sdf.format(date);
        System.out.println("排序后的时间:"+time2);
//        System.out.println("排序之后的数组为:"+ Arrays.toString(arr));
    }

    //基数排序
    //arr为待排序列。temp为10个一维数组
    public static void radixSort(int arr[]){
        //定义中间数组
        int temp[][]=new int[10][arr.length];
        //定义10个索引分别记录10个中间数组的位置
        int indexs[]=new int[10];
        //遍历待排序列,找出最大的数，计算出它的位数
        int max=arr[0];
        for (int i=1;i<arr.length;i++){
            if(max<arr[i]){
                max=arr[i];
            }
        }
        //得到最大的位数
        int digit=(max+"").length();
        //总共只需要digit轮排序
        for(int i=0,n=1;i<digit;i++,n*=10){
            //将每个数放在相应的数组中
            for(int j=0;j<arr.length;j++){
                //计算出每个数相应位上的数值，再选择放在哪个数组中
                int num=arr[j]/n%10;
                temp[num][indexs[num]]=arr[j];
                //将相应的中间数组索引值+1
                indexs[num]++;
            }
            //从10个中间数组中依次取出每个数。放回到原数组中,a来作为arr数组的索引
            for(int j=0,a=0;j<indexs.length;j++){
                if(indexs[j]>0){    //说明这个中间数组里面放了元素
                    //将这个数组里面的元素放入arr中
                    for(int t=0;t<indexs[j];t++){
                        arr[a]=temp[j][t];
                        //arr索引+1
                        a++;
                    }
                    //将中间数组里面的索引置为0
                    indexs[j]=0;
                }
            }
        }
    }

}
